#include <iostream>
#include <cmath>
#include <climits>
#include <windows.h>
#include <chrono>
using namespace std;

int arr[101][10001];

auto init=[]{
    memset(arr,-1,sizeof(arr));
    return 0;
}();

int dfs(int i,int j)
{
    if(i==0)
    {
        return j==0?0:INT_MAX;
    }
    int& res=arr[i][j];
    if(res!=-1)
    {
        return res;
    }
    if(j<i*i)
    {
        res=dfs(i-1,j);
    }
    else
    {
        res=min(dfs(i-1,j),dfs(i,j-i*i)+1);
    }
    return res;
}

class Solution {
public:
    int numSquares(int n) {
        return dfs(sqrt(n),n);
    }
};

void runTest(const string& testName, int n, int expected, Solution& s) {
    cout << testName << "：" << endl;
    cout << "输入：n = " << n << endl;
    
    auto start = chrono::high_resolution_clock::now();
    int result = s.numSquares(n);
    auto end = chrono::high_resolution_clock::now();
    
    auto duration = chrono::duration_cast<chrono::microseconds>(end - start);
    
    cout << "输出：" << result << endl;
    cout << "预期：" << expected << endl;
    cout << "结果：" << (result == expected ? "通过" : "失败") << endl;
    cout << "耗时：" << duration.count() << " 微秒" << endl << endl;
}

int main() {
    SetConsoleOutputCP(CP_UTF8);
    Solution s;
    
    // 测试用例1：完全平方数
    runTest("测试用例1 - 完全平方数", 16, 1, s);
    
    // 测试用例2：两个平方数之和
    runTest("测试用例2 - 两个平方数之和", 13, 2, s);
    
    // 测试用例3：三个平方数之和
    runTest("测试用例3 - 三个平方数之和", 12, 3, s);
    
    // 测试用例4：四个平方数之和
    runTest("测试用例4 - 四个平方数之和", 99, 4, s);
    
    // 测试用例5：小数
    runTest("测试用例5 - 小数", 1, 1, s);
    
    // 测试用例6：较大数
    runTest("测试用例6 - 较大数", 9999, 4, s);

    return 0;
}

